//
//  ProblemMS0809.swift
//  TestProject
//
//  Created by 武侠 on 2021/3/22.
//  Copyright © 2021 zhulong. All rights reserved.
//

import UIKit

/*
 面试题 08.09. 括号
 括号。设计一种算法，打印n对括号的所有合法的（例如，开闭一一对应）组合。

 说明：解集不能包含重复的子集。

 例如，给出 n = 3，生成结果为：

 [
   "((()))",
   "(()())",
   "(())()",
   "()(())",
   "()()()"
 ]
 通过次数14,967提交次数18,374

 */
@objcMembers class ProblemMS0809: NSObject {
    func solution() {
        print(generateParenthesis(3))
    }
    
    /*
     递归
     1: 创建一个数字 left：记录左括号的数量， 创建一个数字 right：记录右括号的数量
     2: 当left == right, 增加一个左括号 left -= 1
     3: 当left < right, 增加一个左括号 left -= 1 或者  增加一个右括号 right -= 1
     4: 不能出现 left > right的情况
     
     */
    func generateParenthesis(_ n: Int) -> [String] {
        return generateParenStr(n, n)
    }
    
    func generateParenStr(_ left: Int, _ right: Int) -> [String] {
        if left == 0 && right == 0 {            // 最后一个 返回"" 必须是空
            return [""]
        } else if left > right {
            return [""]                         // 不合理的
        } else if left == 0 {                   // 只需要 增加右括号
            let array = generateParenStr(left, right-1).map { (str) -> String in
                return ")" + str;
            }
            return array
        } else if left == right {               // 相等时，只能增加左括号
            let array = generateParenStr(left-1, right).map { (str) -> String in
                return "(" + str;
            }
            
            return array
        } else if left > 0, left < right {      // 2中选择
            let array1 = generateParenStr(left-1, right).map { (str) -> String in
                return "(" + str;
            }
            
            let array2 = generateParenStr(left, right-1).map { (str) -> String in
                return ")" + str;
            }
            return array1+array2
        }
        
        return []
    }
}
